Flash memory devices store information with high density on flash memory cells with ever smaller dimensions. In addition, Multi-Level Cells (MLC) may store several bits per cell (bpc) by setting the amount of charge in a cell. Flash memory devices are organized into (physical) pages. Each physical page includes a section allocated for data (e.g., 512 bytes-16 KB and expected larger in the future) and a small amount of spare bytes (e.g., 64-1024 or more bytes for every page) for storing redundancy and metadata. The redundancy bytes are used to store error correcting information, for correcting errors which may have occurred during flash lifetime and the page read process. Each program (write) operation is performed on an entire page. A number of pages are grouped together to form an erase block (also referred to as block). A page cannot be erased unless the entire erase block which includes that page is erased.
One common application of flash memory devices is Secure Digital (SD) cards. Another common application of flash memory devices is Solid State Disks (SSDs). An SSD may typically include a flash memory device and a flash memory controller. The flash memory controller translates commands coming in through the SSD interface into actions (Read/Write/Erase) on the flash memory device. The most common SSD commands may be read commands and write commands of one or more sectors, where a sector may be, but is not limited to, a sequence of 512 bytes.
The read commands or write commands may be of a single sector or multiple sectors. These commands may refer to logical addresses. These addresses may then be redirected to new addresses on the flash memory device which need not directly correspond to the logical addresses that might be referenced by the read or write commands.
This is due to memory management that may be carried out by the flash memory controller in order to support several features such as wear-leveling, bad block management, firmware code and data, error-correction, and others. The erase function is performed on an entire erase block. Because of this functionality, before the data of a selected block may be replaced such as during a write function, the new data must be written in an alternative location before an erase can occur, to preserve the integrity of the stored data.
In some SSDs, the flash memory controller may typically have only a small random access memory (RAM) available for storage. The small size of the RAM limits the type of memory management which may be carried out by the flash memory controller with regard to the data stored in the flash memory device and received from the interface.
The flash memory controller of an SSD may typically manage the flash memory device at the page level. In this approach, each logical page address is associated with an arbitrary physical page address, and the flash memory controller must maintain this association (mapping). In this method, part of the physical space is mapped to logical data, and the rest is set aside for management purposes and is typically named over provisioning. At each time, one or more blocks may be open for writing. When a logical page is to be written, the flash memory controller writes its content into the next available physical page in an open block and updates the physical association of this logical page to the new location. The previous physical location which held the data of this logical address prior to the write is typically designated as obsolete or superseded. The remaining physical pages in a block which are not superseded are called valid physical pages. Once all of the physical pages of an open block are written, a fresh block from the over provisioning is taken, and future writes resume to this block.
Once no more free blocks from the over provisioning are available to host new pages, or the number of free blocks is reduced below some threshold, the flash memory controller begins a process in which valid physical pages from a first block with superseded physical pages are copied into a second empty block, and once no more valid physical pages are left in the first block, the first block is added to the list of free blocks. This process is typically called cleaning.
A logical page designated by a logical page address is read by first looking up its physical address and then reading the data from the physical address which is associated to this logical page.
The flash memory controller may implement a logical to physical (L2P) mapping between a logical page address and a physical page address by means of a L2P table.
The L2P table may be a list of entries that hold, for each logical page which is mapped in the user space, a corresponding physical address.
An example of a prior art L2P table 10 is depicted in FIG. 1. The L2P table 10 includes M entries 10(0)-10(M−1), each entry stores the address of a physical page (physical address) and each entry is pointed by a logical address of a page out of logical pages 0 till (M−1) 20(0)-20(M−1).
FIG. 1 illustrates that the physical pages that are pointed by sequential logical addresses are non-sequential. Thus, L2P table includes the following sequence of physical addresses—physical page 17, physical page 1009, physical page 7289 till physical page 2284.
FIG. 2 illustrates the j′th entry (10, j) of the prior art L2P table 10 of FIG. 1. The j′th entry (10, j) can include a block address 10(j, 1) that is N1 bits long and a page address 10(j, 2) that is N2 bits long. The block address designates the block address and the page address determines the page address within that block.
The number (M) of entries in the L2P table is the number of user-mapped pages, while the size of each entry is the number of bits required to represent the address of each of the physical pages in the disk.
For example, for an SSD with physical size C of 256 GB (2^30 bytes), logical user space U of 256 GB (10^9 bytes), and page size P of 4 KB, the minimal size in bytes required for the complete L2P table is given by:
                              S                      L            ⁢                                                  ⁢            2            ⁢                                                  ⁢            P                          =                              U            P                    *                                    ⌈                                                log                  2                                ⁡                                  (                                      C                    P                                    )                                            ⌉                        /            8                                                  =                                                            256                *                                  10                  ⋀                  9                                                            4                *                                  2                  ⋀                  10                                                      *                                          ⌈                                                      log                    2                                    ⁡                                      (                                                                  256                        *                                                  2                          ⋀                          30                                                                                            4                        *                                                  2                          ⋀                          10                                                                                      )                                                  ⌉                            /              8                                =                      193.7            *                          2              ⋀                              20                ⁢                                                                  [                Bytes                ]                                                        
If pages of size 4 KB are used in an SSD of 256 GB, where 4 bytes are used to hold the physical address of each logical page, then, a L2P table of size 256 MB would be required.
Such large memory requirements may often be accommodated by means of external volatile memory (e.g., DRAM). This requirement introduces additional costs to the complete system. Storing the L2P tables more efficiently can potentially cut down some of these costs.
There is a growing need to reduce the size of the L2P table.